// https://leetcode.cn/problems/target-sum/description/

// 算法思路总结：
// 1. 回溯算法统计目标和的所有表达方式
// 2. 每个数字有正负两种选择，构建二叉树搜索
// 3. 遍历到数组末尾时检查路径和是否等于目标
// 4. 通过回溯维护当前路径和
// 5. 时间复杂度：O(2ⁿ)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int path;
    int ret;
    int _target;
    int findTargetSumWays(vector<int>& nums, int target) 
    {   
        path = ret = 0;
        _target = target;

        dfs(0, nums);

        return ret;
    }

    void dfs(int pos, vector<int>& nums)
    {
        if (pos == nums.size())
        {
            if (path == _target)
            {
                ret++;
            }
            return ;
        }

        path += nums[pos];
        dfs(pos + 1, nums);
        path -= nums[pos];

        path -= nums[pos];
        dfs(pos + 1, nums);
        path += nums[pos];
    }
};

int main()
{
    vector<int> nums1 = {1,1,1,1,1};
    vector<int> nums2 = {1};

    int target1 = 3, target2 = 1;

    Solution sol;

    cout << sol.findTargetSumWays(nums1, target1) << endl;
    cout << sol.findTargetSumWays(nums2, target2) << endl;

    return 0;
}